import java.util.TreeMap;

public class WordDictionary {
    private class Node{
        private boolean isWord;
        private TreeMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            this.next = new TreeMap<>();
        }
        public Node(){
            this(false);
        }
    }

    private Node root;
    public WordDictionary(){
        this.root = new Node();
    }
    /***
     * 向字典树种添加一个单词
     * @param word
     */
    public void addWord(String word){
        Node cur = root;
        for(int i=0;i<word.length();i++){
            Character c = word.charAt(i);
            if(cur.next.get(c) == null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        //先判断此单词是否已经存在
        if(!cur.isWord){
            cur.isWord = true;
        }
    }
    public boolean serach(String words){
        return match(root,words,0);
    }
    private boolean match(Node cur, String word, int index){
        if(index == word.length()){
            return cur.isWord;
        }
        char c = word.charAt(index);
        if(c != '.'){
            if(cur.next.get(c) == null){
                return false;
            }
            return match(cur.next.get(c),word,index+1);
        }else{
            for(char newChar : cur.next.keySet()){
                if(match(cur.next.get(newChar),word,index+1)){
                    return true;
                }
            }
            return false;
        }
    }
}
